1. Technical Field
The present invention relates to a method for interleaving an incoming data stream, a method for de-interleaving an incoming interleaved data stream, interleaving and de-interleaving device, and a communication system.
2. Discussion of Related Art
Such a method for interleaving and de-interleaving, such interleaving and de-interleaving devices and such a communication system are already known in the art, e.g., from the United States patent U.S. Pat. No. 4,559,625 entitled `Interleavers for digital communication` from the inventors Elwyn R. Berlekamp and Po Tong.
In the communication system described in U.S. Pat. No. 4,559,625, an encoding apparatus develops redundant information in a mathematically prescribed manner and adds this redundant information to the data bytes of codewords. The data bytes of several independently encoded codewords then are re-sequenced by an interleaver. In this way, transmission of the codewords over a transmission link becomes more immune for burst noise of long duration. By re-sequencing the data symbols, burst errors are more evenly distributed over independently encoded codewords. As a consequence, error correction through decoding the transmitted codewords is enhanced. Summarizing, the interleaver alters the sequence of data bytes of several codewords to more uniformly distribute the effect of signal degradation or noise on the transmission line over different codewords. In the interleaver, data bytes thereto are entered in memory cells and later on are read out of these memory cells in an order different from the order wherein they entered the memory. The interleaving delay of a data byte is the time interval elapsed between entering and leaving the memory, and usually is expressed as the amount of bytes read out of the memory between the entering and leaving time of the considered data byte. Another important parameter, equal to the number of data bytes in the outgoing interleaved data stream between two data bytes of one and the same codeword, is called the interleaving depth. The interleaving depth is a quantitative indicator of the enhancement of immunity of the transmission for burst noise or the like. In the interleaver described in U.S. Pat. No. 4,559,625, the memory cells wherein data bytes are stored constitute a triangular shaped matrix, i.e. the upper right triangle in the rectangular matrix drawn in FIG. 4a of U.S. Pat. No. 4,559,625. When each row of the triangular shaped matrix is implemented by a first-in-first-out queue, and if incoming data bytes are stored in tail memory cells of the rows while outgoing data bytes are read out of head memory cells of the rows, the interleaving delay of any byte varies linearly related to the ordinal position of the data byte. This is expressed in Col. 2, ln. 34-41 of the cited U.S. patent. In other words, the interleaving delay of a data byte and the ordinate of the row wherein the data byte is stored are linearly interrelated in the known triangular interleaver. The interleaving depth, which defines the noise immunity of the transmission, is constant and determined by the delay increment per row of the matrix. This delay increment is the difference in length between two successive rows of the matrix, expressed as an amount of memory cells.
In a communication system with variable transmit rates, the effect of interleaving on noise immunity of the transmission depends upon the actual transmit rate. If for instance the transmit rate in a first situation is half the transmit rate in a second situation, burst errors of equal duration will damage in the second situation twice the amount of data bytes damaged in the first situation. If the interleaving depth in situation 2 equals that of situation 1, and the error correction codes added to the codewords are the same in both situations, noise immunity in situation 2 expressed as the maximum duration of a burst error which can be rectified, is only half the noise immunity of situation 1. Communication system designers usually have to realize a certain minimum level of erasure correction to accord with standard specifications. The interleaving depth and error correction code length are chosen by the designer to meet this minimum erasure correction level in a worst case scenario. In a communication system with variable transmit rates, this worst case scenario is the situation wherein data are transmitted at the highest allowable transmit rate. If the above described known interleaver is used and data are transmitted at a lower transmit rate, the noise immunity will be better than required, but this is paid by an interleaving delay which is longer than necessary for an exact adjustment of the noise immunity to the minimum required level at this lower transmit rate.